/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, return the bottom-up level order traversal
 *              of its nodes' values. (ie, from left to right, level by level
 *              from leaf to root).
 * 
 *              For example: Given binary tree {3,9,20,#,#,15,7}, 
 *              	    3 
 *                     / \ 
 *                    9  20 
 *                    	/  \
 *                     15   7 
 *              
 *              return its bottom-up level order traversal as: 
 *              [ 
 *              [15,7],
 *              [9,20], 
 *              [3] 
 *              ]
 */
public class BinaryTreePreorderTraversalII {

    private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
	    val = x;
	}
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	if (null == root)
	    return res;
	
	Queue<TreeNode> curLevel = new LinkedList<TreeNode>();
	Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();
	List<Integer> list = new ArrayList<Integer>();
	curLevel.add(root);
	while (!curLevel.isEmpty()) {
	    TreeNode cur = curLevel.poll();
	    list.add(cur.val);
	    
	    if (cur.left != null)
		nextLevel.add(cur.left);
	    if (cur.right != null)
		nextLevel.add(cur.right);
	    
	    if (curLevel.isEmpty()) {
		res.add(0, list);
		list = new ArrayList<Integer>();
		curLevel = nextLevel;
		nextLevel = new LinkedList<TreeNode>();
	    }
	}
    
	return res;
    }

    public void printLevelOrderBottomUsingDFS(TreeNode root) {
	int height = maxHeight(root);
	for (int level = 1; level <= height; level++) {
	    printLevel(root, level);
	    System.out.println();
	}
    }
    
    private void printLevel(TreeNode root, int level) {
	if (null == root)
	    return;
	
	if (1 == level)
	    System.out.print(root.val + ",");
	else {
	    printLevel(root.left, level - 1);
	    printLevel(root.right, level - 1);
	}
    }
    
    private int maxHeight(TreeNode root) {
	if (null == root)
	    return 0;
	
	int leftHeight = maxHeight(root.left);
	int rightHeight = maxHeight(root.right);
	
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    
    @Test
    public void test() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(3);
	TreeNode n4 = new TreeNode(4);
	TreeNode n5 = new TreeNode(5);
	TreeNode n6 = new TreeNode(6);
	n1.left = n2;
	n1.right = n3;
	n2.left = n4;
	n4.left = n5;
	n4.right = n6;

//	List<List<Integer>> res = levelOrderBottom(n1);
//	for (List<Integer> list : res) {
//	    for (int i : list) {
//		System.out.print(i + ",");
//	    }
//	    System.out.println();
//	}
	printLevelOrderBottomUsingDFS(n1);
    }
}
